package h0824;

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr.length > 1) {
           int mid= arr.length/2;
           int[] left=Arrays.copyOfRange(arr,0,mid);
           int[] right=Arrays.copyOfRange(arr,mid,arr.length);
           //排序左边
           mergeSort(left);
           //排序右边
           mergeSort(right);
           marge(arr,left,right);
        }
    }

    private static void marge(int[] arr, int[] left, int[] right) {
        //本质上是合并两个有序数组的过程
        int l=0;
        int r=0;
        int i=0;
        while (l<left.length&&r<right.length){
            if (left[l]<=right[r]){
                arr[i]=left[l];
                l++;
                i++;
            }else {
                arr[i]=right[r];
                r++;
                i++;
            }
        }
        //有可能还有一个数组有剩余
        while (l<left.length){
            arr[i++]=left[l++];
        }
        while (r<right.length){
            arr[i++]=right[r++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}
